// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-05 22:25
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE.segTree;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

@SuppressWarnings("ALl")
class RangeFreqQuery {
    Node root;

    /*-----线段树节点-----*/
    class Node {
        int start, end;
        Map<Integer, Integer> map = new HashMap<>();
        Node left, right;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    /*-----创建线段树方法-----*/
    public Node buildTree(int left, int right) {
        // 创建框架树
        if (left == right) {
            Node node = new Node(left, right);
            return node;
        }
        Node node = new Node(left, right);
        int mid = left + ((right - left) >> 1);
        node.left = buildTree(left, mid);
        node.right = buildTree(mid + 1, right);
        return node;
    }


    public RangeFreqQuery(int[] arr) {
        int n = arr.length;
        root = buildTree(0, n - 1);
        for (int i = 0; i < n; i++) {
            update(arr[i], i, i);
        }
    }

    public void update(int value, int start, int end) {
        update(root, value, start, end);
    }

    private void update(Node root, int value, int start, int end) {
        if (root == null) {
            return;
        }
        root.map.put(value, root.map.getOrDefault(value, 0) + 1);
        int mid = root.start + ((root.end - root.start) >> 1);
        if (mid >= end) {
            update(root.left, value, start, end);
        } else if (mid < start) {
            update(root.right, value, start, end);
        }
        // 因为是单点更新，所以不存在区间
    }

    /*-----线段树查询方法-----*/
    public int query(int left, int right, int value) {
        return query(root, left, right, value);
    }

    private int query(Node root, int left, int right, int value) {
        if (root.start == left && root.end == right) {
            return root.map.getOrDefault(value, 0);
        }
        int mid = root.start + ((root.end - root.start) >> 1);
        if (mid >= right) {
            return query(root.left, left, right, value);
        } else if (mid < left) {
            return query(root.right, left, right, value);
        }
        int leftNum = query(root.left, left, mid, value);
        int rightNum = query(root.right, mid + 1, right, value);
        return leftNum + rightNum;
    }

}

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery obj = new RangeFreqQuery(arr);
 * int param_1 = obj.query(left,right,value);
 * 根据数组创建的数据结构，可以快速查询数组指定区间内指定值的出现频率
 * 从底往上构建线段树，使用HashMap数据结构可以快速定位value
 */